package 动态规划;

/**
 * @description:
 * @author: ywk
 * @date: 2021-01-27
 */
public class 戳气球 {

    static boolean[] visited = new boolean[100];
    static int[] memo = new int[100];
    static int count1 = 0;
    static int count2 = 0;
    static int count3 = 0;

    //1.回溯遍历所有，获取所有的结果
    static int pokeBalloon(int[] nums, int remain, int money) {
        count1++;
        if (remain == 0) {
            System.out.println(money);
            return 0;
        }
        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) {
                continue;
            }
            visited[i] = true;
            int left = i, right = i, leftVal = 0, rightVal = 0;
            while (--left >= 0) {
                if (!visited[left]) {
                    break;
                }
            }
            while (++right <= nums.length - 1) {
                if (!visited[right]) {
                    break;
                }
            }
            if (left == i || left < 0) {
                leftVal = 1;
            } else {
                leftVal = nums[left];
            }
            if (right == i || right > nums.length - 1) {
                rightVal = 1;
            } else {
                rightVal = nums[right];
            }
            money += leftVal * rightVal * nums[i];
            pokeBalloon(nums, remain - 1, money);
            visited[i] = false;
            money -= leftVal * rightVal * nums[i];
        }
        return money;
    }

    //2.回溯遍历所有，只获取最大的结果
    static int pokeBalloonMemo(int[] nums, int remain) {
        count2++;
        int max = Integer.MIN_VALUE;
        if (remain == 0) {
            return 0;
        }
        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) {
                continue;
            }
            visited[i] = true;
            int left = i, right = i, leftVal = 0, rightVal = 0;
            while (--left >= 0) {
                if (!visited[left]) {
                    break;
                }
            }
            while (++right <= nums.length - 1) {
                if (!visited[right]) {
                    break;
                }
            }
            if (left == i || left < 0) {
                leftVal = 1;
            } else {
                leftVal = nums[left];
            }
            if (right == i || right > nums.length - 1) {
                rightVal = 1;
            } else {
                rightVal = nums[right];
            }
            max = Math.max(pokeBalloonMemo(nums, remain - 1) + leftVal * rightVal * nums[i], max);
            visited[i] = false;
        }
        return max;
    }

    static int pokeBalloonDp(int[] nums) {
        int n = nums.length;
        // 添加两侧的虚拟气球
        int[] points = new int[n + 2];
        points[0] = points[n + 1] = 1;
        for (int i = 1; i <= n; i++) {
            points[i] = nums[i - 1];
        }        // base case 已经都被初始化为 0
        int[][] dp = new int[n + 2][n + 2];
        // 开始状态转移
        // i 应该从下往上
        for (int i = n; i >= 0; i--) {
            // j 应该从左往右
            for (int j = i + 1; j < n + 2; j++) {
                // 最后戳破的气球是哪个？
                for (int k = i + 1; k < j; k++) {
                    // 择优做选择
                    dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + points[i] * points[j] * points[k]);
                }
            }
        }
        return dp[0][n + 1];
    }
}
